Modular operations according to the Montgomery method enable the performance of modular computations in a finite Galois field without carrying out any division. The finite Galois field is denoted as GF(2.sup.n), with 2.sup.n elements. These operations are applicable to cryptography for the authentication of messages, the identification of a user, and the exchange of cryptographic keys. Exemplary applications are described in the French patent application No. 2,679,054.
There are commercially available integrated circuits dedicated to such applications, e.g., the product ST16CF54 made by SGS-THOMSON Microelectronics. To carry out modular computations, a dedicated arithmetic coprocessor is used as described in the European patent application No. 601,907. In the implementation of modular operations by the dedicated coprocessor, it is necessary to produce a binary parameter J0 encoded on an integer number Bt of bits, such that [(J0+N0)+1]mod 2.sup.Bt =0 with N0 as an odd integer number encoded on Bt bits and mod representing the modulo.
Methods have already been proposed by the assignee of the present invention to produce the parameter J0 using a dedicated circuit, thus enabling this parameter to be computed at a high speed in an integrated circuit. These methods are described in the European patent application 0 778 518 published on Jun. 11, 1996. This application corresponds to the patent application filed Dec. 3, 1996 in the United States under number Ser. No. 08/759,892. An important factor in the performance of modular operations is the computation time needed to produce the desired result.